1. Field of the Invention
The present invention provides a method of balancing delay in a circuit design that modifies one or all of the wiring paths to make the paths traverse wire segments of about the same length and orientation, within each wiring level that the paths traverse, and to traverse such segments in the same order.
2. Description of the Related Art
A significant source of delay variation in paths on an integrated circuit is variation (due predominantly to variations in the manufacturing process) of characteristics, such as height, width, and spacing, of the metal wires used to interconnect the circuit elements of the integrated circuit. These interconnecting wires are typically composed of segments on multiple wiring layers (a net is a collection of connected net segments which forms a connection between two or more circuit elements). To maximize the usability of the available space on these wiring layers and to reduce the tendency for one wire segment to block the desired path of another wire segment on the same wiring layer, wire segments on one layer are typically oriented solely or predominantly in a single direction (e.g., all horizontal or all vertical). Wire segments on adjacent layers are typically oriented in different directions, usually perpendicular to each other. Therefore, to create a wiring connection between two points which are neither horizontally nor vertically aligned, a pair of wire segments on two wiring layers is generally used, with a via, or interlayer connection, used to connect the layers at the “bend” in the wiring route. Multiple horizontal and vertical segments may also be used in such connections by introducing additional “bends” in the wiring route, although there may be benefit in yield, and other respects, in reducing the number of such bends. Other sets of wiring directions are sometimes used, so that some wiring layers may be preferentially used for wire segments oriented at a 30, 60, or 45 degree angle to the predominant wire segment direction on some other wiring layer.
The above-mentioned wire characteristics whose variation results in delay variation tend to be well-correlated among different wire segments on the same wiring layer because these different wire segments are manufactured together during the same set of manufacturing steps. However wire characteristics of wire segments on different wiring levels tend to be very poorly correlated, because they are created during different sets of manufacturing steps. These variations in the characteristics of wire segments on a particular wiring layer will normally cause variations in electrical parameters of wire segments on that layer, and in particular in their resistance and capacitance. Wire variations which increase wire resistance, such as reductions in wire width or thickness, will often cause decreases in wire capacitance, and vice versa. The source to sink delay of a multiple wire segment net will increase with increases in both wire segment capacitance and resistance. But an increase in resistance in a wire segment near a net source will cause a larger delay increase than a similar resistance increase in a wire segment near the net sink, because more of the net capacitance must be charged or discharged through that wire segment resistance when a signal transition occurs. Similarly, an increase in the capacitance of a wire segment near a net sink will cause a larger delay increase than a similar capacitance increase in a wire segment near the net source, because the current which charges or discharges the wire segment capacitance must pass through more of the net resistance when a signal transition occurs.
Thus nets which have wire segments on different wiring layers, have different length wire segments on the same wiring layers, or have wire segments of the same lengths on the same wiring levels, but in different orders, will exhibit different delay variations. As an example, consider the delay of two nets, each with a 1 mm segment of M5 (metal on level 5), a 1 mm segment of M6, and a sink capacitance of 100 fF, and where both metal levels have a nominal resistance of 100 ohms per mm and a nominal capacitance of 1 pF per mm. In the first net the M5 segment precedes (is closer to the net source than) the M6 segment, and in the second net the M6 segment precedes the M5 segment. According to the well-known Elmore delay approximation, if R1 and R2 are the resistances of the first and second wire segments, respectively, C1 and C2 are the capacitances of the first and second wire segments, respectively, and C1 is the load capacitance, the net delay will beD=R1*(C1/2+C2+C1)+R2*(C2/2+C1).
With the values given above, both nominal net delays is (in seconds)Dnom=1E2*(1E-12/2+1E-12+1E-13)+1E2*(1E-12/2+1E-13), orDnom=220 ps.
If, however, some process variation causes the M5 resistance to increase by 10%, the M5 capacitance to decrease by 10%, the M6 resistance to decrease by 10%, and the M6 capacitance to increase by 10%, the first net delay would become:Dvar1=1.1E2*(9E-13/2+1.1E-12+1E-13)+9E*(1.1E-12/2+1E-13), orDvar1=240 ps, andDvar2=9E1*(1.1E-12/2+9E-13+1E-13)+1.1E2*(9E-13/2+1E-13), orDvar2=200 ps.
Thus nets with matching delays under nominal conditions can result in significantly different delays under process variation (+/−9% for 10% parameter variations, in this example). Although the above delay estimations were performed using the Elmore delay formula for simplicity, similar results are obtained using more accurate methods such as moment matching or circuit simulation. The fundamental issue is that the even if the delay functions for two nets match at a particular point, unless net characteristics such as the levels orders and lengths of wire segments are matched, they may have different sensitivities to or derivatives with respect to various process parameters, and thus different delays in the presence of process variation.
Correct operation of a digital integrated circuit requires that set up and hold tests between clock and data signals at latches and flip-flops in the integrated circuit be satisfied, or more generally, that specific ordering relationships (hereafter referred to collectively as timing tests) between the arrival times of various pairs of signals within the integrated circuit be satisfied. The signal arrival times involved in these timing tests are functions of the delays of various nets and circuit elements along the paths or signal fanin cones. A signal fanin cone is the collection of circuit elements, all of whose outputs directly or indirectly feed the signal. The delays of these circuit elements and nets are themselves functions of many parameters, including wire characteristics whose variation was described above. To ensure that timing tests are satisfied in the presence of process variation, it is important that the variation in the difference between the delays of the two paths involved in the test be minimized. Typically both paths or cones involved in a timing test include a clock delay portion, in one case to the clock pin of the latch or flip-flop from which data signals are launched, and in the other case to the clock pin of the latch or flip-flop at which data signals are captured, and at which the timing test is performed. Since a latch or flip-flop will be involved in both launching and capturing data, and may be involved in both critical setup and hold tests, the clock delay portion will generally have both upper bounds and lower bounds imposed by timing tests. A good way to improve the probability of passing timing tests in the presence of process variation is to try to minimize the variation in the difference in delay between all pairs of launch and capture clock paths involved in critical (close to failing) timing tests.
One common method of minimizing the differences in delay and delay variation is by the use of H-trees, as shown in FIG. 1. More specifically, FIG. 1 shows balanced H-trees which extend from R. Nodes labeled 1 form a first level H-tree and nodes labeled 2 form four second level H-trees connected to ends of the first level H-tree. But such tress may not be possible to construct if there are blockages, and may waste wiring resource and power if the distribution of clock sinks (e.g., latches or flip-flops) is spatially not uniform.
Another method of balancing (minimizing the differences in) the delay of paths is described in U.S. Pat. No. 5,339,253 by Carrig et al., in “Exact zero skew”, Ren-Song Tsay, ICCAD 1991, pp. 336-339, and in “Zero skew clock routing with minimum wirelength” by Ting-Hai Chao et al. in IEEE Transactions on Circuits and Systems II, November 1992, pp. 799-814, which are incorporated herein by reference. These methods build a distribution tree to a set of sinks with relative arrival time targets by iteratively pairing sinks, connecting them, and determining a point along the wire interconnecting them from which to drive the pair such that the relative arrival time targets for the sinks are met (i.e., that the difference in delays from the driving point to the sinks equals the difference in the target arrival times of the sinks). This drive point then becomes a sink for a successive iteration of the method, with a target arrival time equal to the target arrival time of either sink minus the delay from the drive point to that sink. The criteria for pairing sinks generally attempts to minimize the maximum distance between the sinks of any pair, and/or to minimize the total wire length used to connect all pairs. These methods are able to adapt to blockages and nonuniform sink distributions, but do not address reducing variation in delay differences in the presence of parameter variation.
A related conventional method is described in “Optimal buffered clock tree synthesis” by Jae Chung et al. in the 1994 IEEE International ASIC Conference and Exhibit, pp. 130-133, which attempts to minimize the sensitivity of the net delay to process variation by choosing a wire width which makes the derivative of delay with respect to width equal to zero. However this may require a wire width which is not practical to implement, and does not directly address the variation in the difference between pairs of net delays. It also eliminates delay variation only in the neighborhood around the ideal chosen point, and hence a large variation in wire segment parameters, which can happen in practice, may still cause a significant variation in delay.